قصد داريم چند مساله را که بيشتر جنبه رياضي دارند، حل كرده و برنامه آنها را بنويسيم. بي‌شک يکي از تاثيرگذار‌ترين رشته‌ها در علوم کامپيوتر، رياضي است. پس بد نيست كمي ديد رياضي خود را گسترش دهيم تا بتوانيم برنامه‌هايي بنويسيم که مسائل رياضي را بسادگي و در کمترين زمان ممكن حل کنند.
مساله اول: برنامه‌اي بنويسيد که 2 عدد را گرفته و بزرگ‌ترين مقسوم‌عليه مشترک آنها را چاپ کند.
چند روش براي محاسبه بزرگ‌ترين مقسوم‌عليه مشترک يا همان ب.م.م وجود دارد. يکي از روش‌ها اين است که بياييم تمام مقسوم‌عليه‌هاي 2 عدد را محاسبه کنيم و سپس اعداد مشترک را حساب کرده و در يک مجموعه ذخيره کنيم و بزرگ‌ترين عضو آن را به عنوان ب.م.م در نظر بگيريم. حال نکته اين است که آيا اين روش، روشي بهينه است؟ يعني مي‌توان راهي راحت‌تر و بهتر از اين ارائه داد؟
پاسخ «آري» است. يکي ديگر از روش‌هاي محاسبه ب.م.م روش نردباني يا همان روش تقسيمات متوالي است. در روش تقسيمات متوالي عدد بزرگ‌تر را بر عدد کوچک‌تر تقسيم مي‌کنيم، اگر خارج قسمت برابر صفر شد، عدد کوچک‌تر ب.م.م است و اگر صفر نشد، مقسوم عليه را به عنوان عدد بزرگ‌تر در نظر مي‌گيريم و باقيمانده را به‌عنوان عدد کوچک‌تر و سپس عدد بزرگ‌تر را بر عدد کوچک‌تر تقسيم مي‌کنيم، آنقدر اين کار را تكرار مي‌كنيم که باقيمانده برابر صفر شود. وقتي باقيمانده برابر صفر شد، عدد بزرگ‌تر که مقسوم عليه مرحله پيشين است را به عنوان ب.م.م در نظر مي‌گيريم.
int num1 = 48, num2 = 16, max , min, temp = 1;
max = num1 » num2 ? num1 : num2;
min = num1 « num2?num1:num2;
while (temp != 0) {
temp = max % min;
max = min;
min = temp;
}
cout «« max;
مساله دوم: مقدار تابع نمايي يک عدد را محاسبه كنيد.
منظور از تابع نمايي، تابع e به‌توان x است. براي محاسبه اين تابع مي‌توان از بسط تيلور اين تابع که به‌صورت زير است، استفاده كرد:
خب، حال اگر بخواهيم سري را حساب کنيم، نياز به يک حلقه داريم تا تک‌تک جملات سري را حساب كرده و با جملات قبلي جمع کنيم. در مواقعي که نياز به محاسبه يک‌سري است بايد به اين نکته توجه داشت که سري همگراست يا واگرا. اگر واگرا بود جوابي براي مساله وجود نخواهد داشت چون هيچ وقت حلقه ما به پايان نمي‌رسد، ولي اگر همگرا بود، مي‌توان با گذاشتن يک شرط تمام شدن آن را نشان داد. مثلا تفاضل جمله nام با جمله
n-1ام از يک عدد بسيار کوچکي کمتر باشد يا شرايطي از اين دست.
بسيار خب، برگرديم به مساله خودمان. مي‌دانيم که اين سري همگراست چون درجه رشد
!X از x به توان n بيشتر است، پس هميشه به ازاي مقادير بزرگ، حاصلي کوچک‌تر از يك توليد مي‌شود. مقدار همگرايي سري برابر جواب مساله يعني همان مقدار تابع e به توان x است. خب حال مساله اين است كه چگونه سري را حساب کنيم؟
مي‌دانيم که رشد عدد
!x بسيار زياد است مثلا !1000 يک عدد 154 رقمي مي‌شود و مي‌دانيم که متغيري به اين اندازه در زبان‌هاي برنامه‌نويسي وجود ندارد و اگر هم وجود داشته باشد، ميزان حافظه اشغالي زيادي نياز دارد.
راهحل اين مساله، استفاده از آرايه است که در شماره‌هاي قبلي در مورد آن توضيح داده شد.
يعني
!1000 را با يک آرايه پياده‌سازي کنيم و همين‌طور !1001 و اعداد ديگر و اعمال رياضي را روي اين اعداد انجام دهيم. اين راهحل منطقي نيست و زمان‌بر است، اما آيا اين تنها راهحل است؟ پاسخ «نه» است.
در اين مقاله قصد داريم راهحل ديگري ارائه دهيم که هم سرعت بيشتري دارد و هم حافظه مصرفي کمتري. در اين راهحل براي محاسبه جمله كنوني از جمله پيشين استفاده مي‌کنيم. اين روش چند مزيت دارد چون از جمله قبلي استفاده مي‌شود، به اين صورت که اگر در مرحله Nام باشيم و حاصل عبارت X باشد براي محاسبه جمله
n+1 نيازي نداريم که X به توان N+1 تقسيم بر !(N+1) را حساب کنيم. کافي است جمله nام را در X/N+1 ضرب کنيم. با اين روش ديگر نيازي به محاسبه اعداد بزرگ نيست و جواب را با کمترين ميزان حافظه مصرفي و سرعت بيشتري پيدا مي‌کنيم. مانند کد زير:
const double epmax = 0.00000000000000005;
double number = 2, n = 0, newer = 0, older = 1, sum = 1;
while (older » epmax) {
n++;
newer = older * (number / n);
sum = sum + newer;
older = newer;
}
کد واضح است، مي‌دانيم جملات سري در حال کوچک‌تر شدن هستند و در هر مرحله بررسي مي‌کنيم که آيا مقدار older که آخرين جمله است از يک عدد بسيار کوچک بزرگ‌تر باشد. اگر کوچک‌تر باشد از حلقه خارج مي‌شود و مقدار sum همان همگرايي سري و مقدار تابع e به توان x است که همان جواب مساله ماست.
منابع: www.ehow.com و en.wikipedia.org
اميربهاءالدين سبط‌الشيخ
عضو شوید
عضویت سریع
آمار مطالب
آمار بازدید
آمار
وب سایت:
